# 118. 杨辉三角
# 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

# 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

# ![img](/Users/apple/Desktop/test/leetcode/assets/1626927345-DZmfxB-PascalTriangleAnimated2.gif)

#  

# 示例 1:

# 输入: numRows = 5
# 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
# 示例 2:

# 输入: numRows = 1
# 输出: [[1]]


# 提示:

# 1 <= numRows <= 30

# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/pascals-triangle
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


from time import time
from typing import List


class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # 解法1
        res = []
        for i in range(1, numRows+1):            
            if i<=2:
                res.append([1]*i)
            else:
                tmp = []
                for j in range(1,i-1):
                    tmp.append(res[i-2][j-1]+res[i-2][j])
                res.append([1]+tmp+[1])
                del(tmp)
        return res

        # 解法2
        # res = [[] for i in range(numRows)]
        # for i in range(1, numRows+1):
        #     for j in range(i):
        #         if i<3:
        #             res[i-1].append(1)
        #         elif j == 0 or j == i-1:
        #             res[i-1].append(1)
        #         else:
        #             res[i-1].append(res[i-2][j-1]+res[i-2][j])
        # return res

    
if __name__ == '__main__':
    start = time()
    a = Solution()
    print(a.generate(numRows = 1))
    print(a.generate(numRows = 2))
    print(a.generate(numRows = 5))
    print(a.generate(numRows = 10))
    # print(a.generate(numRows = 30))
    end = time()
    print('='*40)
    print("start time is ", start*1000)
    print("end   time is ", end*1000)
    print("耗时:",end*1000 - start*1000,"ms")